package 力扣;

import java.util.Arrays;

//给出一个无重叠的 ，按照区间起始端点排序的区间列表。
//
//在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
public class 插入区间 {
    public static void main(String[] args) {
        int[][] ints={};
        int[] newInt={1,5};
        int[][] ints1 = insert(ints, newInt);
        for (int[] m: ints1
             ) {
            System.out.println(Arrays.toString(m));

        }
    }
    public static int[][] insert(int[][] intervals, int[] newInterval) {

         int n=intervals.length;
         if (n==0)
             return new int[][]{newInterval};
         //新建一个数组长度为n+1的二维数组
        int[][] res = new int[n + 1][2];
        int i=0;
        //循环，如果插入数组的第一个元素大于，intervals数组的第一个元素，则后移
        for (int[] m : intervals) {
           if ( m[0]<newInterval[0] && m[1]<newInterval[0] || m[0]>newInterval[0] && m[0]>newInterval[1])
               res[i++]=m;
           else  {
               res[i++] = new int[]{Math.min(m[0],newInterval[0]), Math.max(m[1], newInterval[1])};
               newInterval = new int[]{Math.min(m[0],newInterval[0]), Math.max(m[1], newInterval[1])};
           }
        }
        int len=res.length;
        int[][] ints = new int[len][2];
        int idx=-1;
        for (int[] m : res) {
            if (idx==-1 || ints[idx][1]<m[0])
                ints[++idx]=m;
            else
                ints[idx][1]=Math.max(m[1],ints[idx][1]);
        }
        return Arrays.copyOf(ints,idx+1);
    }
}
